這章節要來介紹一個新的ADT(Abstract Data Type)叫做Priority Queue。

大家應該都知道Queue的特性了，就是先進先出，像我們平常排隊一樣，先排的就是先輪到你進店內。

那Priority Queue就是又多加了一個極值的特性，假設是Minimum Priority Queue，就是當我們從Queue裡poll出元素時，會拿到最小的元素，remove也是刪掉最小的元素。

以下是Min Priority Queue的ADT：

public interface MinPQ<Item> {
	/** Adds the item to the priority queue. */
	public void add(Item x);
	/** Returns the smallest item in the priority queue. */
	public Item getSmallest();
	/** Removes the smallest item from the priority queue. */
	public Item removeSmallest();
	/** Returns the size of the priority queue. */
	public int size();
}

那我們該如何實現這個ADT呢？如果使用BST，最佳情況就是Θ(logN)，而且還是保持bushy的情況下。有沒有更好的解法？

那就要來提提另一種資料結構，Heap。

以上圖片是以min-heap來舉例，當然也可以把min-heap的規則變成max-heap。

Binary min-heap要遵守以下兩條規則：

1. Min-heap：所有的節點都要比自己兩個小孩還要小或相等。（最右邊的違反了）
2. Complete：樹狀結構可以有空缺的節點，但是空缺只能出現在最底層，而且所有節點一定是先往左邊加，所以不會有空缺在左邊而右邊有節點的情況。（第三個違反了）

可以看到binary min-heap的root恰恰好就會是最小的元素(因為min-heap的特徵)，所以當我們getSmallest()就可以Θ(1)拿到～

接著可能就會好奇，那add跟removeSmallest會如何進行呢？

首先我們來看看add：

由於complete的規則，當我們加入元素時，一定會先往最底層、最左邊來加，也就是下圖的位置。但是會發現加完後不會是正確的binary min-heap：

所以我們會一步一步校正這顆元素，直到他到正確的位置，所以他就會開始往上游：

上一張圖往上游了一層，但還是不對，所以繼續往上游：

游完後來檢視一下，看來是沒問題了，所以就在此完成了add的流程：

接著來看看removeSmallest：

由於最小的元素就是root，所以第一步肯定就是先幹掉root：

接著這步就很有意思了，由於complete的特性，我們為了盡量保持binary min-heap的結構，拿最後加入的那個位置的元素來補root是最合適的：

接下來的動作就跟add很像了，開始讓元素游到他最適合的位置：

再繼續游：

然後就完成removeSmallest了：

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License